package alo.p3.work;

import alo.p3.ListNode;

import java.util.ArrayList;
import java.util.List;

//判读循环链表是否回文
public class IfHuiWen {
     boolean IfHuiWen(ListNode head) {
        ListNode slow = head, fast = head,head1,head2;
        while (fast.getNext() != head && fast.getNext().getNext() != head) {
            slow = slow.getNext();
            fast = fast.getNext().getNext();
        }
        //奇偶校验无用
        /*//如果结点数为奇数
        if (fast.getNext() == head) {
        } else {
            //如果结点为偶数
            fast = fast.getNext();
        }*/
        head1 = head;
        head2 = slow.getNext();
        //逆置
        head2 = ReverseList(head2);

        //比较
        while (head1!=null&&head2!=null){
            if (head1.getData()==head2.getData()){
                head1=head1.getNext();
                head2=head2.getNext();
            }else
                return false;

        }
        return true;

    }

    //判断链表是否回文
    //这种做法有一些问题，原链表顺序被破坏了
    public boolean isPalindrome(ListNode head) {
        boolean result;
        if(head==null||head.getNext()==null) result=true;
        ListNode slow=head,fast=head,head2=null;

        while(fast.getNext()!=null&&fast.getNext().getNext()!=null){
            slow=slow.getNext();
            fast=fast.getNext().getNext();
        }
        //奇偶校验没有用
        /*
        //结点个数为偶数
        if(fast==null)
            head2=slow;
        else//结点个数为奇数
        */
        ListNode end1=slow;
        head2=slow.getNext();
        //逆置链表
        ListNode start2=head2;
        head2=ReverseList(head2);
        while(head!=null&&head2!=null){
            if(head.getData()==head2.getData()){
                head=head.getNext();
                head2=head2.getNext();
            }else
                result=false;
        }
        result=true;
        //恢复链表
        end1.setNext(ReverseList(start2));
        return result;
    }


    //判断链表是否回文
    class Solution {
        public boolean isPalindrome(ListNode head) {
            if (head == null) {
                return true;
            }

            // 找到前半部分链表的尾节点并反转后半部分链表
            ListNode firstHalfEnd = endOfFirstHalf(head);
            ListNode secondHalfStart = reverseList(firstHalfEnd.getNext());

            // 判断是否回文
            ListNode p1 = head;
            ListNode p2 = secondHalfStart;
            boolean result = true;
            while (result && p2 != null) {
                if (p1.getData() != p2.getData()) {
                    result = false;
                }
                p1 = p1.getNext();
                p2 = p2.getNext();
            }

            // 还原链表并返回结果
            firstHalfEnd.setNext(reverseList(secondHalfStart));
            return result;
        }

        private ListNode reverseList(ListNode head) {
            ListNode prev = null;
            ListNode curr = head;
            while (curr != null) {
                ListNode nextTemp = curr.getNext();
                curr.setNext(prev);
                prev = curr;
                curr = nextTemp;
            }
            return prev;
        }

        private ListNode endOfFirstHalf(ListNode head) {
            ListNode fast = head;
            ListNode slow = head;
            while (fast.getNext() != null && fast.getNext().getNext() != null) {
                fast = fast.getNext().getNext();
                slow = slow.getNext();
            }
            return slow;
        }
    }
    //把链表的值复制到数组中（空间复杂度O（n））
    class Solution2{
        public boolean isPalindrome(ListNode head) {
            List<Integer> array=new ArrayList<Integer>();
            ListNode c1=head;
            while (c1!=null){
                array.add(c1.getData());
                c1=c1.getNext();
            }
            int k=0;
            int j=array.size()-1;
            while (k<j){
                if (array.get(k).equals(array.get(j))){
                    k++;
                    j--;
                }else return false;
            }
            return true;
        }
    }


    //使用递归的方式
    class solution3{
        private ListNode frontPointer;

        private boolean recursivelyCheck(ListNode currentNode) {
            if (currentNode != null) {
                if (!recursivelyCheck(currentNode.getNext())) {
                    return false;
                }
                if (currentNode.getData() != frontPointer.getData()) {
                    return false;
                }
                frontPointer = frontPointer.getNext();
            }
            return true;
        }

        public boolean isPalindrome(ListNode head) {
            frontPointer = head;
            return recursivelyCheck(head);
        }

    }



    ListNode ReverseList(ListNode headNode){
        ListNode temp=null,nextNode=null;
        while (headNode!=null){
            nextNode=headNode.getNext();//2,3,4
            headNode.setNext(temp);//1->null,2->1,3->2
            temp=headNode;//1,2,3
            headNode=nextNode;//head=2,head=3,head=4
        }
        return temp;
    }
}
